package com.example.sort;

import cn.hutool.core.util.ArrayUtil;

import java.util.Arrays;
import java.util.Random;

public class QuickSort {
    public static void main(String[] args) {
        int length = 20;

        int[] arrs = init(length);

        System.out.println(Arrays.toString(arrs));
        System.out.println("---------------------------------");
        sort(arrs, 0, arrs.length - 1);
//        System.out.println(Arrays.toString(arrs));
    }

    private static int[] init(int length) {
        Random random = new Random();
        int[] arrs = new int[length];
        int i = 0;
        while (ArrayUtil.contains(arrs, 0)) {
            int next = random.nextInt(1000) + 1;
            if (ArrayUtil.contains(arrs, next)) {
                continue;
            }
            arrs[i] = next;
            i++;
        }
        return arrs;
    }

    private static void sort(int[] arrs, int left, int right) {
        if (left < right) {
            //Swap(s[l], s[(l + r) / 2]);
            //将中间的这个数和第一个数交换 参见注1
            int i = left, j = right, x = arrs[left];
            while (i < j) {
                // 从右向左找第一个小于x的数
                while (i < j && arrs[j] >= x) {
                    j--;
                }
                if (i < j) {
                    arrs[i++] = arrs[j];
                }
                // 从左向右找第一个大于等于x的数
                while (i < j && arrs[i] < x) {
                    i++;
                }
                if (i < j) {
                    arrs[j--] = arrs[i];
                }
            }
            arrs[i] = x;
            sort(arrs, left, i - 1); // 递归调用
            sort(arrs, i + 1, right);
        }
    }
}
